package 二叉树系列;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Connect {
    public Node connect(Node root) {
        Deque<Node> deque = new LinkedList<>();
        if(root==null) return null;
        deque.push(root);
        while(!deque.isEmpty()){
            int len = deque.size();

            Node nextNode = null;
            for(int i=0;i<len;i++){
                Node node = deque.pollFirst();
                nextNode = deque.peek();
                if(i!=len-1){
                    node.next = nextNode;
                }else{
                    node.next = null;
                }
                if(node.left!=null) deque.addLast(node.left);
                if(node.right!=null) deque.addLast(node.right);
            }
        }
        return root;
    }
    class Solution {
        public Node connect(Node root) {
            Deque<Node> deque = new LinkedList<>();
            if(root==null) return null;
            deque.push(root);
            while(!deque.isEmpty()){
                int len = deque.size();

                Node nextNode = null;
                for(int i=0;i<len;i++){
                    Node node = deque.pollFirst();
                    nextNode = deque.peek();
                    if(i!=len-1){
                        node.next = nextNode;
                    }else{
                        node.next = null;
                    }
                    if(node.left!=null) deque.addLast(node.left);
                    if(node.right!=null) deque.addLast(node.right);
                }
            }
            return root;
        }
    }
}
